package training;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_8_23_Training {
    //包含所有 1 的最小矩形面积 II
    public int minimumSum(int[][] grid) {
        int[] re = m1(grid);
        int ans = Integer.MAX_VALUE;

        for(int i = re[0];i < re[1];i++) {
            ans = Math.min(
                    ans,
                    m0(grid, re[0], i, re[2], re[3]) + cal(grid, i + 1, re[1], re[2], re[3])
            );

            ans = Math.min(
                    ans,
                    m0(grid, i + 1, re[1], re[2], re[3]) + cal(grid, re[0], i, re[2], re[3])
            );
        }

        for(int j = re[2];j < re[3];j++) {
            ans = Math.min(
                    ans,
                    m0(grid, re[0], re[1], re[2], j) + cal(grid, re[0], re[1], j + 1, re[3])
            );

            ans = Math.min(
                    ans,
                    m0(grid, re[0], re[1], j + 1, re[3]) + cal(grid, re[0], re[1], re[2], j)
            );
        }

        return ans;
    }

    int cal(int[][] grid, int x0, int x1, int y0, int y1) {
        if(x0 == x1 && y0 == y1) return 1;
        int re = Integer.MAX_VALUE;

        for(int i = x0;i < x1;i++) {
            re = Math.min(
                    re,
                    m0(grid, x0, i, y0, y1) + m0(grid, i + 1, x1, y0, y1)
            );
        }

        for(int j = y0;j < y1;j++) {
            re = Math.min(
                    re,
                    m0(grid, x0, x1, y0, j) + m0(grid, x0, x1, j + 1, y1)
            );
        }

        return re;
    }

    public int m0(int[][] grid, int xUp, int xDown, int yLeft, int yRight) {
        int x0 = xUp;
        for(;x0 <= xDown;x0++) {
            boolean find = false;
            for(int j = yLeft;j <= yRight;j++) {
                if(grid[x0][j] == 1) {
                    find = true;
                    break;
                }
            }
            if(find) break;
        }

        int x1 = xDown;
        for(;x1 >= xUp;x1--) {
            boolean find = false;
            for(int j = yLeft;j <= yRight;j++) {
                if(grid[x1][j] == 1) {
                    find = true;
                    break;
                }
            }
            if(find) break;
        }

        int y0 = yLeft;
        for(;y0 <= yRight;y0++) {
            boolean find = false;
            for(int i = xUp;i <= xDown;i++) {
                if(grid[i][y0] == 1) {
                    find = true;
                    break;
                }
            }
            if(find) break;
        }

        int y1 = yRight;
        for(;y1 >= yLeft;y1--) {
            boolean find = false;
            for(int i = xUp;i <= xDown;i++) {
                if(grid[i][y1] == 1) {
                    find = true;
                    break;
                }
            }
            if(find) break;
        }

        return (x1 - x0 + 1) * (y1 - y0 + 1);
    }

    public int[] m1(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int x0 = 0;
        for(;x0 < n;x0++) {
            boolean find = false;
            for(int j = 0;j < m;j++) {
                if(grid[x0][j] == 1) {
                    find = true;
                    break;
                }
            }
            if(find) break;
        }

        int x1 = n - 1;
        for(;x1 >= 0;x1--) {
            boolean find = false;
            for(int j = 0;j < m;j++) {
                if(grid[x1][j] == 1) {
                    find = true;
                    break;
                }
            }
            if(find) break;
        }

        int y0 = 0;
        for(;y0 < m;y0++) {
            boolean find = false;
            for(int i = 0;i < n;i++) {
                if(grid[i][y0] == 1) {
                    find = true;
                    break;
                }
            }
            if(find) break;
        }

        int y1 = m - 1;
        for(;y1 >= 0;y1--) {
            boolean find = false;
            for(int i = 0;i < n;i++) {
                if(grid[i][y1] == 1) {
                    find = true;
                    break;
                }
            }
            if(find) break;
        }

        return new int[]{x0, x1, y0, y1};
    }
}
